<!DOCTYPE html>
<html lang="en">
<head>
	<meta charset="UTF-8">
	<title>两数之和</title>
</head>
<body>
	<script>
	/**
	 * 给定一个整数数组 nums 和一个目标值 target
		在该数组中找出和为目标值的两个整数，并返回他们

		要求时间复杂度：O(n)

		思路：利用 map 存储已遍历的元素 (典型的空间换时间)
	 */
	// 时间复杂度O(n)、 空间复杂度O(n)
	function twoNumAdd(arr, target) {
	  if (Array.isArray(arr)) {
	    // 使用map将遍历过的数字存起来
	    let map = {};
	    for (let i = 0; i < arr.length; i++) {
	      // 从map中查找是否有key 等于 target-nums[i]，如果取到了，则条件成立，返回结果
	      if (map[target - arr[i]] !== undefined) {
	        return [target - arr[i], arr[i]];
	      } else {
	        // 条件不成立，则将已遍历的值存起来
	        map[arr[i]] = i;
	      }
	    }
	  }
	  return [];
	}

	console.log(twoNumAdd([8, 2, 6, 5, 4, 1, 3], 7)); // [2, 5]
	</script>
</body>
</html>